package com.tgy.algorithm.base;

import java.util.Arrays;

// 归并排序
class MergeSort {

    public static void mergeSort(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }
        doMergeSort(arr, 0, arr.length - 1);
    }

    public static void doMergeSort(int[] arr,int left,int right) {
        if (left >=  right) {
            return;
        }
        int mid = left + ((right - left) >> 2);
        doMergeSort(arr, left, mid);
        doMergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {

        int[] temp = new int[right - left + 1];
        int index = 0;
        int preIndex= left;
        int postIndex = mid + 1;
        while (preIndex <= mid && postIndex <= right) {
            if (arr[preIndex] < arr[postIndex]) {
                temp[index++] = arr[preIndex++];
            }else {
                temp[index++] = arr[postIndex++];
            }
        }

        while (preIndex <= mid) {
            temp[index++] = arr[preIndex++];
        }

        while (postIndex <= right) {
            temp[index++] = arr[postIndex++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
    }

    public static void mergeSort2(int[] arr) {

        if(arr == null || arr.length < 2) {
            return;
        }

        int step = 1;
        int allStep = step << 1;
        int i;
        while (step < arr.length) {
            i = 0;
            while (i < arr.length) {
                // 4 +
                int lastIndex = i + allStep - 1;
                if (lastIndex > arr.length - 1) {
                    lastIndex = arr.length - 1;
                }
                // 4 + 2
                if(i + step > arr.length -1) {
                    // 剩余的数一半都不到，因为一半是已经排好序的，所以不需要排序了，直接退出
                    break;
                }
                merge(arr,i, i + step - 1,lastIndex);
                i += allStep;
            }

            step = step << 1;
            allStep = step << 1;
        }
    }

    public static void mergeSort3(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        int halfStep = 1;
        int allStep = halfStep << 1;
        int length = arr.length;
        int i = 0;
        int rightIndex;
        // 1 , 3, 2, 6,0
        while (halfStep < length) {
            i = 0;
            while (i < length) {
                rightIndex = i + allStep - 1;
                if (rightIndex > length - 1) {
                    rightIndex = length - 1;
                }

                if (i + halfStep > length - 1) {
                    break;
                }
                merge(arr,i,i+ halfStep - 1,rightIndex);
                i += allStep;
            }

            halfStep = halfStep << 1;
            allStep = halfStep << 1;
        }
    }

    // 获取最小数之和，获取小于当前数之前的数之和
    public static int getMinSum(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }

        // 3 2 4 2 1
        // 3 前面没有
        // 2 前面没有
        // 4 前面 3 2
        // 2 前面 没有
        // 1 前面没有数

        // 这个问题等价于找到当前数之后大于当前数的数量count,最后的和就是 cur * count 的和
        // 3 * 1 后面 4
        // 2 * 1 后面 4
        // 4 * 0
        // 2 * 0
        // 1 * 0

        // 3 2 ｜ 4 2  ｜ 1
        // 2 3 3 4 ｜ 2 2 2 4 1
        // 2 2 3 4 1
        //
        return 0;
    }

    public static int mergeArr01(int[] nums, int left, int mid, int right) {
        int[] tmpNums = new int[right - left + 1];
        int leftIndex = left;
        int rightIndex = mid + 1;
        int index = 0;
        int sum = 0;
        while (leftIndex <= mid && rightIndex <= right) {
//            tmpNums[index++]
            sum += (nums[leftIndex] < nums[rightIndex] ? nums[leftIndex] * (right - rightIndex + 1):0);
            tmpNums[index++] = nums[leftIndex] < nums[rightIndex] ? nums[leftIndex++] : nums[rightIndex++];
        }

        // 2,
        // 2,3, 2,3,4
        while(leftIndex <= mid) {
            tmpNums[index++] = nums[leftIndex++];
        }

        while (rightIndex <= right) {
            tmpNums[index++] = nums[rightIndex++];
        }

        for (int i = 0; i < tmpNums.length; i++) {
            nums[left + i] = tmpNums[i];
        }

        return sum;
    }

    public static int mergeSort01(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        return doMergeSort01(nums,0,nums.length - 1);
    }

    public static int doMergeSort01(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + ((right - left) >> 2);
        return doMergeSort01(nums,left,mid) + doMergeSort01(nums,mid + 1,right) + mergeArr01(nums,left,mid,right);
    }
    // 逆序队
    // 2,3,1,2,4,2
    // (2,1),(3,1),(3,2),(3,2),(4,2)

}

public class _归并排序 {
    public static void main(String[] args) {
        // 4,5,2,3,2,3
        int[] nums = new int[]{3,1,2,3,1,0,2};
        // 2
        // 3 1 2 3 1 0 2
//        MergeSort.mergeSort(nums);
//        MergeSort.mergeSort3(nums);
//        System.out.println(Arrays.toString(nums));
        int result = MergeSort.mergeSort01(nums);
        System.out.println(result);
    }
}
